package com.example.hashtable;

import java.util.*;

/**
 * 给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
 *
 *  示例 1:
 * 输入:"tree"
 * 输出:"eert"
 * 解释:
 * 'e'出现两次，'r'和't'都只出现一次。
 * 因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。
 *
 *  示例 2:
 * 输入:"cccaaa"
 * 输出:"cccaaa"
 * 解释:
 * 'c'和'a'都出现三次。此外，"aaaccc"也是有效的答案。
 * 注意"cacaca"是不正确的，因为相同的字母必须放在一起。
 */
public class Leetcode451_FrequencySort {
    public static void main(String[] args) {
        System.out.println(new Solution().frequencySort("aacbabc"));
    }

    static class Solution {

        /**
         * 最大堆
         * 首先，遍历字符串，使用HashMap统计各个字符出现的次数(key为字符串里的不同字符,value为其出现的次数)
         * 然后，建立一个大根堆(根据在Map中的频率大小)
         * 最后，大跟堆不断出堆拼接结果
         * @param s
         * @return
         */
        private String frequencySort3(String s) {
            StringBuilder res = new StringBuilder();
            Map<Character, Integer> map = new HashMap<>(); // key为字符串里的不同字符,value为其出现的次数
            char[] chars = s.toCharArray();
            // 统计各个字符出现的频率并更新最大频率值
            for (int i = 0; i < chars.length; i++) {
                int frequency = map.getOrDefault(chars[i], 0) + 1;
                map.put(chars[i], frequency);
            }

            // 建立一个大根堆(根据在Map中的频率大小)
            Queue<Character> maxHeap = new PriorityQueue<>((c1, c2) -> map.get(c2) - map.get(c1));
            Iterator<Character> iterator = map.keySet().iterator();
            while (iterator.hasNext()) { // 将map的元素入堆
                maxHeap.offer(iterator.next());
            }

            // 拼接结果
            while (!maxHeap.isEmpty()) {
                Character tmp = maxHeap.poll();
                int count = map.get(tmp);
                for (int i = 0; i < count; i++) {
                    res.append(tmp);
                }
            }

            return res.toString();
        }

        /**
         * 桶排序改进(使用StringBuilder数组 代替 TreeMap)
         * @param s
         * @return
         */
        private String frequencySort2(String s) {
            StringBuilder res = new StringBuilder();
            Map<Character, Integer> map = new HashMap<>(); // key为字符串里的不同字符,value为其出现的次数
            char[] chars = s.toCharArray();
            int maxFrequency = 0;
            // 统计各个字符出现的频率并更新最大频率值
            for (int i = 0; i < chars.length; i++) {
                int frequency = map.getOrDefault(chars[i], 0) + 1;
                map.put(chars[i], frequency);
                maxFrequency = Math.max(maxFrequency, frequency);
            }

//            map.forEach((k, v) -> System.out.println("k: " + k + " v: " + v));

            // 用频率进行桶排序
            StringBuilder[] buckets = new StringBuilder[maxFrequency + 1];
            for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                Character key = entry.getKey();
                Integer frequency = entry.getValue();
                if (buckets[frequency] == null) buckets[frequency] = new StringBuilder();
                buckets[frequency].append(key);
            }

            for (int i = buckets.length - 1; i >= 0; i--) {
                StringBuilder tmp = buckets[i];
                if (tmp != null) {
                    for (int j = 0; j < tmp.length(); j++) {
                        for (int k = 0; k < i; k++) {
                            res.append(tmp.charAt(j));
                        }
                    }
                }
            }
            return res.toString();
        }

        /**
         * 解法一:桶排序 + TreeMap
         *
         * 首先，遍历字符串，使用HashMap统计各个字符出现的次数(key为字符串里的不同字符,value为其出现的次数)
         * 然后，遍历得到的HashMap，使用TreeMap对频率进行排序(key字符频率,value为频率相同的字符组成的list)
         * 最后，遍历TreeMap拼接得到字符后反转返回
         *
         * @param s
         * @return
         */
        private String frequencySort1(String s) {
            StringBuilder res = new StringBuilder();
            Map<Character, Integer> map = new HashMap<>(); // key为字符串里的不同字符,value为其出现的次数

            char[] chars = s.toCharArray();
            int maxFrequency = 0;
            // 统计各个字符出现的频率并更新最大频率值
            for (int i = 0; i < chars.length; i++) {
                int frequency = map.getOrDefault(chars[i], 0) + 1;
                map.put(chars[i], frequency);
                maxFrequency = Math.max(maxFrequency, frequency);
            }

//            map.forEach((k, v) -> System.out.println("k: " + k + " v: " + v));

            // 用频率进行桶排序
            Map<Integer, List<Character>> bucket = new TreeMap<>();// key字符频率,value为频率相同的字符组成的list
            for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                Character key = entry.getKey();
                Integer frequency = entry.getValue();
                bucket.computeIfAbsent(frequency, (f) -> new ArrayList<>()).add(key);
            }

            bucket.forEach((k, v) -> v.forEach(e -> {
                    for (int i = 0; i < k; i++) {
                        res.append(e);
                    }
                }));

            return res.reverse().toString();
        }

        public String frequencySort(String s) {
            return frequencySort3(s);
        }
    }
}
